Heap Operations (Insertion, Deletion, Heapify)

Heap হল একটি বিশেষ ধরনের বাইনারি ট্রি ডাটা স্ট্রাকচার যা complete binary tree (পূর্ণ বাইনারি ট্রি) এর বৈশিষ্ট্য ধারণ করে। এতে একটি নির্দিষ্ট ordering property থাকে যা এটি Max-Heap বা Min-Heap হিসেবে পরিচিত করে।

• Max-Heap: যেখানে প্রতিটি প্যারেন্ট নোডের মান তার চাইল্ড নোডের মানের চেয়ে বেশি বা সমান থাকে।
• Min-Heap: যেখানে প্রতিটি প্যারেন্ট নোডের মান তার চাইল্ড নোডের মানের চেয়ে কম বা সমান থাকে।

Heap অপারেশনগুলি যেমন Insertion, Deletion, এবং Heapify অত্যন্ত গুরুত্বপূর্ণ। এগুলি Priority Queue তে ব্যবহৃত হয় এবং sorting algorithms যেমন Heap Sort এ ব্যবহৃত হয়।

এই টিউটোরিয়ালে আমরা Heap এর সাধারণ অপারেশনগুলি যেমন Insertion, Deletion, এবং Heapify সম্পর্কে আলোচনা করব এবং সেগুলি Java তে কিভাবে বাস্তবায়িত করা যায়, তা দেখাব।

1. Heap Structure Overview

• Complete Binary Tree: Heap একটি পূর্ণ বাইনারি ট্রি হতে হবে, যার মানে হল যে এটি একটি বাইনারি ট্রি যেখানে সমস্ত স্তরের শেষ স্তর ছাড়া সব স্তরের নোড পূর্ণ থাকে। শেষ স্তরের নোডগুলি বাম থেকে ডানে পূর্ণ হবে।
• Heap Property:
  • Max-Heap: প্যারেন্ট নোডের মান চাইল্ড নোডের মানের চেয়ে বড় বা সমান।
  • Min-Heap: প্যারেন্ট নোডের মান চাইল্ড নোডের মানের চেয়ে ছোট বা সমান।

2. Heap Operations

Heap এর তিনটি গুরুত্বপূর্ণ অপারেশন হল:

• Insertion: একটি নতুন উপাদান যুক্ত করা।
• Deletion: সর্বোচ্চ বা সর্বনিম্ন মানের উপাদান মুছে ফেলা।
• Heapify: গাছের অবস্থা বজায় রাখতে Heapify অপারেশনটি ব্যবহার করা হয়।

3. Insertion in Heap

Heap এ নতুন উপাদান ইনসার্ট করার জন্য, প্রথমে উপাদানটি গাছের শেষ স্তরে যোগ করা হয় এবং তারপর সেটিকে উপরের দিকে সঠিক স্থানে নিয়ে আসা হয় (যাকে বলা হয় heapify-up বা bubble-up) যাতে Heap Property বজায় থাকে।

3.1. Insertion Algorithm

1. নতুন উপাদানকে গাছের শেষ স্তরে যোগ করুন।
2. প্যারেন্ট নোডের সাথে নতুন উপাদানের মান তুলনা করুন:
   • যদি Max-Heap হয়, এবং নতুন উপাদান প্যারেন্ট নোডের চেয়ে বড় হয়, তবে প্যারেন্ট নোডের সাথে তাদের স্থান বদলান।
   • যদি Min-Heap হয়, এবং নতুন উপাদান প্যারেন্ট নোডের চেয়ে ছোট হয়, তবে প্যারেন্ট নোডের সাথে তাদের স্থান বদলান।
3. এই প্রক্রিয়া চলতে থাকবে যতক্ষণ না নতুন উপাদানটি সঠিক অবস্থানে পৌঁছায়।

3.2. Insertion Example in Java (Max-Heap)

import java.util.Arrays;

public class MaxHeap {
    private int[] heap;
    private int size;
    
    public MaxHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    // Method to insert a new element
    public void insert(int value) {
        if (size == heap.length) {
            System.out.println("Heap is full");
            return;
        }
        
        // Insert the value at the last position
        heap[size] = value;
        size++;
        
        // Heapify-up
        heapifyUp(size - 1);
    }

    // Method to heapify the tree from bottom to top
    private void heapifyUp(int index) {
        while (index > 0 && heap[index] > heap[(index - 1) / 2]) {
            // Swap with parent node
            int temp = heap[index];
            heap[index] = heap[(index - 1) / 2];
            heap[(index - 1) / 2] = temp;

            index = (index - 1) / 2;
        }
    }

    // Method to print the heap
    public void printHeap() {
        System.out.println(Arrays.toString(Arrays.copyOfRange(heap, 0, size)));
    }

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.insert(10);
        maxHeap.insert(20);
        maxHeap.insert(5);
        maxHeap.insert(30);
        maxHeap.insert(15);

        maxHeap.printHeap();
    }
}

ব্যাখ্যা:

• insert() মেথডে উপাদানটি শেষ স্তরে যোগ করা হয়, এবং তারপর heapifyUp() মেথডের মাধ্যমে উপাদানটি সঠিক অবস্থানে নিয়ে আসা হয়।

আউটপুট:

[30, 20, 5, 10, 15]

4. Deletion in Heap

Heap থেকে উপাদান মুছে ফেলার জন্য, সাধারণত সর্বোচ্চ বা সর্বনিম্ন মান (রুট নোড) মুছে ফেলা হয়। মুছে ফেলার পর, গাছের শেষ উপাদানটি রুটে এনে heapify-down প্রক্রিয়া শুরু করা হয় যাতে Heap Property বজায় থাকে।

4.1. Deletion Algorithm

1. রুট নোডটি মুছে ফেলুন এবং গাছের শেষ উপাদানটি রুটে বসান।
2. নতুন রুট উপাদানটির সাথে প্যারেন্ট-চাইল্ড সম্পর্ক সঠিক রাখতে heapify-down অপারেশন প্রয়োগ করুন।
3. উপাদানটি সঠিক স্থানে পৌঁছানো না পর্যন্ত এই প্রক্রিয়া চালিয়ে যান।

4.2. Deletion Example in Java (Max-Heap)

public void delete() {
    if (size == 0) {
        System.out.println("Heap is empty");
        return;
    }

    // Replace the root with the last element
    heap[0] = heap[size - 1];
    size--;

    // Heapify down from the root
    heapifyDown(0);
}

private void heapifyDown(int index) {
    int leftChild = 2 * index + 1;
    int rightChild = 2 * index + 2;
    int largest = index;

    // Find the largest among root, left child, and right child
    if (leftChild < size && heap[leftChild] > heap[largest]) {
        largest = leftChild;
    }
    if (rightChild < size && heap[rightChild] > heap[largest]) {
        largest = rightChild;
    }

    // Swap if needed and continue heapifying down
    if (largest != index) {
        int temp = heap[index];
        heap[index] = heap[largest];
        heap[largest] = temp;

        heapifyDown(largest);
    }
}

ব্যাখ্যা:

• delete() মেথডে রুট নোডটি মুছে ফেলা হয় এবং শেষ উপাদানটি রুটে বসানো হয়। এরপর heapifyDown() মেথডের মাধ্যমে গাছের অবস্থা সঠিক রাখা হয়।

5. Heapify Operation

Heapify অপারেশন হল একটি প্রক্রিয়া যার মাধ্যমে একটি অপর্যাপ্ত গাছকে Max-Heap বা Min-Heap এ রূপান্তরিত করা হয়। সাধারণত, এটি দুটি ভাগে হয়ে থাকে:

• heapify-up: এটি ইনসার্ট অপারেশনে ব্যবহৃত হয়, যেখানে নতুন উপাদান গাছের শেষে যোগ করার পর, সেটি উপরের দিকে উঠানো হয়।
• heapify-down: এটি ডিলিশন অপারেশনে ব্যবহৃত হয়, যেখানে গাছের শীর্ষে থাকা উপাদানটি মুছে ফেলা হয় এবং গাছের শেষ উপাদানটি শীর্ষে এনে নিচে নামানো হয়।

5.1. Heapify Example (Max-Heap)

private void heapifyDown(int index) {
    int leftChild = 2 * index + 1;
    int rightChild = 2 * index + 2;
    int largest = index;

    // Find the largest among root, left child, and right child
    if (leftChild < size && heap[leftChild] > heap[largest]) {
        largest = leftChild;
    }
    if (rightChild < size && heap[rightChild] > heap[largest]) {
        largest = rightChild;
    }

    // Swap if needed and continue heapifying down
    if (largest != index) {
        int temp = heap[index];
        heap[index] = heap[largest];
        heap[largest] = temp;

        heapifyDown(largest);
    }
}

ব্যাখ্যা:

• heapifyDown() মেথডটি গাছের নোডটি সঠিক স্থানে পৌঁছাতে সাহায্য করে যাতে Heap Property বজায় থাকে।

সারাংশ

Heap একটি গুরুত্বপূর্ণ ডাটা স্ট্রাকচার যা গাছের আকারে থাকে এবং বিশেষত Priority Queue এবং Heap Sort এর জন্য ব্যবহৃত হয়। এর মধ্যে Insertion, Deletion, এবং Heapify অপারেশনগুলি গুরুত্বপূর্ণ।

• Insertion অপারেশনটি গাছের শেষে উপাদান যোগ করে এবং heapify-up এর মাধ্যমে সঠিক স্থানে নিয়ে আসে।
• Deletion অপারেশনটি রুট নোড মুছে ফেলে এবং heapify-down এর মাধ্যমে গাছের অবস্থান ঠিক রাখে।
• Heapify অপারেশনটি গাছকে Max-Heap বা Min-Heap এ রূপান্তরিত করতে ব্যবহৃত হয়।

এই অপারেশনগুলি ব্যবহার করে, Heap ডাটা স্ট্রাকচারটি priority scheduling, sorting algorithms, এবং graph algorithms এর মতো বিভিন্ন ক্ষেত্রে ব্যবহৃত হয়।